package com.hardy.basic;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * Author: Hardy
 * Date:   2021/1/20
 * Description:
 **/
public class Array {

    // 快排交换
    public void fastSort1(int[] a, int l, int r) {
        if (l >= r) return;

        int v = a[l];
        int i = l, j = r;

        while (i < j) {
            while (i < j && a[j] > v) j--;
            while (i < j && a[i] <= v) i++;
            swap(a, i, j);
        }
        swap(a, l, i);

        fastSort1(a, l, i - 1);
        fastSort1(a, i + 1, r);
    }

    // 快排填坑
    public void fastSort2(int[] a, int l, int r) {
        if (l >= r) return;

        int v = a[l];
        int i = l, j = r;

        while (i < j) {
            while (i < j && a[j] > v) j--;
            a[i] = a[j];

            while (i < j && a[i] <= v) i++;
            a[j] = a[i];
        }
        a[i] = v;

        fastSort2(a, l, i - 1);
        fastSort2(a, i + 1, r);
    }

    // 删除排序数组中的重复项
    public int removeDuplicates(int[] nums) {
        int i = 0;
        for (int j = 1; j < nums.length; j++) {
            if (nums[i] < nums[j]) {
                swap(nums, ++i, j);
            }
        }
        System.out.println(Arrays.toString(nums));
        return i + 1;
    }

    // 27 移除元素
    public int removeElement(int[] nums, int val) {
        // 方案一
        int i = 0;
        for (int j = 0; j < nums.length; j++) {
            if (i == j && nums[j] != val) i++;    // 查找第一个要移除的元素
            if (i < j && nums[j] != val) swap(nums, i++, j);
        }

        // 方案二
        //int i = 0;
        //for (; i < nums.length; i++) {
        //    if (nums[i] == val) break;
        //}

        //if (i >= nums.length) return nums.length;

        //for (int j = i + 1; j < nums.length; j++) {
        //    if (nums[j] == val) continue;
        //    swap(nums, i++, j);
        //}

        System.out.println(Arrays.toString(nums));
        return i;
    }

    //下一个排列
    public void nextPermutation(int[] nums) {
        // 3 2 1 5 4 > 3 2 4 1 5  5 3 4 2 1 > 5 4 1 2 3  5 4 3 2 1 > 1 2 3 4 5

        // 查找降序发生的位置
        int i = nums.length - 2;
        for (; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) break;
        }

        // 逆序
        if (i == 0) {
            reverse(nums, 0, nums.length - 1);
            return;
        }

        // 查找降序发生的位置的数大且最近接
        int j = nums.length - 1;
        for (; j > i; j--) {
            if (nums[i] < nums[j]) break;
        }

        // 交换i <> j
        swap(nums, i, j);

        // 逆序i之后的
        reverse(nums, i + 1, nums.length - 1);
    }

    // 全排列
    public void fullPermutation(int[] nums) {
        int l = nums.length;
        // 转换成位图，假设 len=3 -> 000 ~ 111
        for (int i = 1; i <= 1 << l - 1; i++) {
            StringBuffer sb = new StringBuffer();
            for (int j = 0; j < l; j++) {
                // 判断 j位 在不在位图中
                if ((i & 1 << j) == 0) continue;
                sb.append(nums[j]);
            }
            System.out.println(sb.toString());
        }
    }

    // 34. 在排序数组中查找元素的第一个和最后一个位置
    public int[] searchRange(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        int mid = (l + r) / 2;

        while (l < r) {
            if (nums[mid] == target) break;

            if (nums[mid] < target) l = mid + 1;
            else r = mid - 1;

            mid = (l + r) / 2;
        }

        // 未查到
        if (nums[mid] != target) return new int[]{-1, -1};
        // 查到一个
        if (l == r) return new int[]{l, r};

        // 查左
        int mr = mid;
        while (l < mr) {
            int t = (l + mr) / 2;

            if (nums[t] == target) mr = t;
            else l = t + 1;
        }

        int ml = mid;
        while (ml < r) {
            int t = (ml + r) / 2 + 1;

            if (nums[t] == target) ml = t;
            else r = t - 1;
        }

        return new int[]{l, r};
    }

    // 4. 寻找两个正序数组的中位数
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int l1 = nums1.length;
        int l2 = nums2.length;

        //int is = (l1 + l2) % 2;
        //int mid = (l1 + l2) / 2;  // [1 2 3]/2 = 1; [1 2 3 4]/2 = (2, 2 - 1)
        //int k = mid + 1;          // [1 2 3] > (mid+1) = (2); [1 2 3 4] > (mid, mid+1) = (2, 3)
        int k = (l1 + l2) / 2 + 1;

        int i = 0;
        int j = 0;
        int n = 0;
        int m = 0;

        while (k > 0) {
            m = Math.max(m, n);

            // 边界
            if (i == l1) {
                if (k >= 2) {
                    m = Math.max(nums2[j + k - 2], m);
                    n = nums2[j + k - 1];
                } else {
                    n = nums2[j];
                }
                break;
            }

            // 边界
            if (j == l2) {
                if (k >= 2) {
                    m = Math.max(nums1[i + k - 2], m);
                    n = nums1[i + k - 1];
                } else {
                    n = nums1[i];
                }
                break;
            }

            // 边界
            if (k == 1) {
                m = Math.max(m, n);
                n = Math.min(nums1[i], nums2[j]);
                break;
            }

            // 特殊处理
            int t = k / 2;
            int idx1 = Math.min(l1 - 1, i + t - 1);
            int idx2 = Math.min(l2 - 1, j + t - 1);

            if (nums1[idx1] <= nums2[idx2]) {
                k = k - (idx1 - i + 1);
                n = nums1[idx1];
                i = idx1 + 1;
            } else {
                k = k - (idx2 - j + 1);
                n = nums2[idx2];
                j = idx2 + 1;
            }
        }
        return (l1 + l2) % 2 == 1 ? n : (m + n) / 2.0;
    }

    // 215. 数组中的第K个最大元素
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(k);
        for (int i : nums) {
            if (queue.size() < k) {
                queue.offer(i);
                continue;
            }
            if (queue.peek() > i) continue;

            queue.poll();
            queue.offer(i);
        }
        return queue.poll();
    }

    // 215. 数组中的第K个最大元素
    public int findKthLargestFastSort(int[] nums, int k) {
        return findKthLargestFastSort(nums, 0, nums.length - 1, k);
    }

    public int findKthLargestFastSort(int[] nums, int l, int r, int k) {
        int t = nums[l];
        int i = l, j = r;

        while (i < j) {
            while (nums[j] > t && i < j) j--;
            while (nums[i] <= t && i < j) i++;
            swap(nums, i, j);
        }
        swap(nums, l, i);

        if (i == k - 1) return nums[i];
        if (i > k - 1) return findKthLargestFastSort(nums, l, i - 1, k);
        else return findKthLargestFastSort(nums, i + 1, r, k);
    }

    public void reverse(int[] a, int i, int j) {
        for (; i < j; i++, j--) swap(a, i, j);
    }

    public void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }


    public static void main(String[] args) {
        int[] a = {3, 2, 1, 5, 6, 4};

        Array main = new Array();

        //arr.fastSort2(a, 0, a.length - 1);
        //System.out.println(Arrays.toString(a));

        //arr.searchRange(a, 8);
        //System.out.println(Arrays.toString(a));

        //main.removeDuplicates(a);
        System.out.println(main.findKthLargest(a, 2));
        System.out.println(main.findKthLargestFastSort(a, a.length - 2 + 1));
    }
}
